import java.util.LinkedList;
import java.util.Queue;

/**
 * You're given a directed graph in the form of an Adjacency Matrix Your goal is
 * to find the maximum flow given a source and sink node.
 * 
 * Remember this is a directed graph, so matrix[i][j] doesn't always equal
 * matrix[j][i]. matrix[][] is a square matrix and the number of nodes in the
 * graph is equal to the dimension of the matrix.
 * 
 * We will only be grading this based on the value you return. This means you
 * may code it however you want. (There are many different ways to implement
 * these algorithms)
 * 
 * Remember, don't change any headers like in previous homeworks.
 * 
 * * * * * * * * * * *
 * 
 * You may assume that every graph has at least two nodes, and that source and
 * sink are two valid distinct nodes. capacity[i][j] having a value of 0
 * represents that there is no edge going from vertex i to vertex j. Note that
 * cost[i][j] has no meaning if capacity[i][j] is initially 0 and it should
 * be ignored
 * 
 * * * * * * * * * * *
 * 
 * These are not necessarily algorithms we've gone over. You will have to do a
 * little research to code these.
 * 
 * * * * * * * * * * *
 * 
 * Example:
 * 
 * int[][] matrix = {{0,2}, {0,0}}; 
 * int[][] cost = {{0, 4}, {0, 0}};
 * 
 * MaxFlow.maxFlow(matrix, 0, 1) should return 2 
 * MaxFlow.minCost(matrix, cost, 0, 1) should return 8
 * 
 */
public class MaxFlow {

	/**
	 * Max Flow (Ford Fulkerson / Edmonds Karp)
	 * 
	 * This method returns the maximum flow through a graph.
	 * 
	 * @param capacity
	 * @param source
	 * @param sink
	 * @return
	 */
	public static int maxFlow(int[][] capacity, int source, int sink)
    {

        int maxFlow = 0;
        int flow;
        int verticesNumber = capacity[0].length;

        Queue<Integer> queue = new LinkedList<Integer>();
        int[] parents = new int[verticesNumber];
        boolean[] visited = new boolean[verticesNumber];

        int[][] newGraph = new int[verticesNumber][verticesNumber];
        newGraph = capacity;

        int i, j;
        while (canBreadthFirstSearch(newGraph,parents,visited,queue,source,sink, verticesNumber))
        {
            flow = Integer.MAX_VALUE;
            for (j = sink; j != source; j = parents[j])
            {
                i = parents[j];
                flow = Math.min(flow, newGraph[i][j]);
            }
            for (j = sink; j != source; j = parents[j])
            {
                i = parents[j];
                newGraph[i][j] -= flow;
                newGraph[j][i] += flow;
            }
            maxFlow += flow;
        }

        return maxFlow;
	}

    public static boolean canBreadthFirstSearch(int[][] graph, int[] parents, boolean[] visited,  Queue<Integer> queue, int source, int sink, int verticesNumber)
    {

        boolean pathFound = false;
        int destination, element;

        for(int vertex = 0; vertex < verticesNumber; vertex++)
        {
            parents[vertex] = -1;
            visited[vertex] = false;
        }

        queue.add(source);
        parents[source] = -1;
        visited[source] = true;

        while (!queue.isEmpty())
        {
            element = queue.remove();
            destination = 1;

            while (destination < verticesNumber)
            {
                if (graph[element][destination]
                > 0 &&  !visited[destination-1])
                {
                    parents[destination] = element;
                    queue.add(destination);
                    visited[destination] = true;
                }
                destination++;
            }
        }
        if(visited[sink-1])
        {
            pathFound = true;
        }
        return pathFound;
    }

	/**
	 * Min-Cost Max-Flow
	 * 
	 * This method returns the minimum cost of the maximum flow through a graph.
	 * The cost of putting a single unit of flow through an edge i,j is
	 * cost[i][j]
	 * 
	 * @param capacity
	 * @param cost
	 * @param source
	 * @param sink
	 * @return
	 */
	public static int minCost(int[][] capacity, int[][] cost, int source, int sink) {
		return -7;
	}
}